|
In computer science, the shunting-yard algorithm is a method for parsing mathematical expressions specified in infix notation. It can be used to produce output in Reverse Polish notation (RPN) or as an abstract syntax tree (AST). The algorithm was invented by Edsger Dijkstra and named the "shunting yard" algorithm because its operation resembles that of a railroad shunting yard. Dijkstra first described the Shunting Yard Algorithm in the Mathematisch Centrum report (MR 34/61 ). Like the evaluation of RPN, the shunting yard algorithm is stack-based. Infix expressions are the form of mathematical notation most people are used to, for instance 3+4 or 3+4 *(2−1). For the conversion there are two text variables (strings), the input and the output. There is also a stack that holds operators not yet added to the output queue. To convert, the program reads each symbol in order and does something based on that symbol. The shunting-yard algorithm has been later generalized into operator-precedence parsing. ==A simple conversion== :Input: 3+4 #Add 3 to the output queue (whenever a number is read it is added to the output) #Push + (or its ID) onto the operator stack #Add 4 to the output queue #After reading the expression, pop the operators off the stack and add them to the output. # In this case there is only one, "+". #Output 3 4 + This already shows a couple of rules: * All numbers are added to the output when they are read. * At the end of reading the expression, pop all operators off the stack and onto the output. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Shunting-yard algorithm」の詳細全文を読む スポンサード リンク
|